package com.captain.leetcode.回溯算法;

import java.util.*;

/**
 * Des:
 * <p>
 * 给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
 * <p>
 * 解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
 * <p>
 * 示例 1：
 * <p>
 * 输入：nums = [1,2,2]
 * 输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
 * 示例 2：
 * <p>
 * 输入：nums = [0]
 * 输出：[[],[0]]
 *
 * @author XL
 * @Date 2021/8/12 14:31
 */
public class 子集II90 {

    public static void main(String[] args) {
        int[] arr = new int[]{1,2,2};
        new 子集II90().subsetsWithDup(arr).forEach(System.out::println);

    }
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        if (Objects.isNull(nums) || nums.length == 0) return new ArrayList<>();
        //排序
        Arrays.sort(nums);
        int len = nums.length -1 ;
        List<List<Integer>> res = new ArrayList<>();
        Deque path = new ArrayDeque<>();
        int[] oldIndex = new int[nums.length];
        dfs(nums,len,0,path,res,oldIndex);
        return res;
    }

    //递归
    private void dfs(int[] nums, int len, int index, Deque path, List<List<Integer>> res, int[] oldIndex) {
        //回溯条件
        res.add(new ArrayList<>(path));
        if (index > len) return;
        //逻辑处理
        for (int i = index; i <= len; i++) {
            //1 1 2 2
            //横向除去重复数据,这样把向下重复的数字也除去了 1 2 2
            //oldIndex[i - 1] == 0 说明:肯定是第一行存在重复值, 直接排除
            if (i > 0 && nums[i - 1] == nums[i] && oldIndex[i - 1] == 0) continue;
            oldIndex[i] = 1;
            path.add(nums[i]);
            //向下继续遍历
            dfs(nums,len, i+1,path,res,oldIndex);
            //回退
            oldIndex[i] = 0;
            path.removeLast();
        }
    }
}
